; Exercise 1.23
; The smallest-divisor procedure shown at the start of this section does lots
; of needless testing: After it checks to see if the number is divisible by 2
; there is no point in checking to see if it is divisible by any larger even
; numbers. This suggests that the values used for test-divisor should not be
; 2, 3, 4, 5, 6, . . . , but rather 2, 3, 5, 7, 9, . . . . To implement this
; change, define a procedure next that returns 3 if its input is equal to 2 and
; otherwise returns its input plus 2. Modify the smallest-divisor procedure
; to use (next test-divisor) instead of (+ test-divisor 1). With timed-
; prime-test incorporating this modified version of smallest-divisor, run the
; test for each of the 12 primes found in [Exercise 1-22], page 54. Since this
; modification halves the number of test steps, you should expect it to run
; about twice as fast. Is this expectation confirmed? If not, what is the
; observed ratio of the speeds of the two algorithms, and how do you explain
; the fact that it is different from 2?
(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))
(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))
(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (next test-divisor)))))
(define (divides? a b)
  (= (remainder b a) 0))
(define (prime? n)
  (= n (smallest-divisor n)))
(define (next n)
  (if (= n 2)
      3
      (+ n 2)))
; 10000000019 *** .26
; 10000000033 *** .22999999999999998
; 10000000061 *** .22999999999999998
; 100000000003 *** .6500000000000001
; 100000000019 *** .6799999999999997
; 100000000057 *** .6700000000000004
; 1000000000039 *** 2.0399999999999996
; 1000000000061 *** 1.9900000000000002
; 1000000000063 *** 2.0199999999999996
; A expectativa não é confirmada. Observa-se uma redução de 1:0.65 no tempo.
; A quantidade de passos caiu, mas o que é feito em cada passo aumentou.
; (> (square test-divisor) n) 1
; (divides? test-divisor n)   1
; (= (remainder b a) 0))      2
; (= n (smallest-divisor n))) 1
; Total 5 operações antes que passaram para 7 com a verificação do if e a 
; soma da função next. Essa variação junto com a redução pela metade dos
; passos seria responsável por uma redução de 1:0.7
